class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 根据前缀和思想，设一个位置前缀和为sum，sum-前缀和 == k的区间即为所求
        // 利用哈希求有多少个 sum-前缀和 == k的区间
        int n = nums.size(), sum = 0, ret = 0;;
        unordered_map<int, int> hash(n); // 左int存前缀和，右int存前缀和出现次数
        hash[0] = 1; // 初始化前缀和为0的次数为1（整个数组等于K的情况）
        for(int i = 0; i < n; ++i)
        {
            sum += nums[i]; // 计算i位置的前缀和
            if(hash[sum - k] != 0) // 判断i位置前缀和-k是否存在
            {
                ret += hash[sum - k];
            }
            hash[sum]++; // 计算i之前只保存i-1
        }
        return ret;
    }
};